package priv.pront.code.national.acwing.graph;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class A849_Dijkstra求最短路堆优化 {
    static int[] dis,w,h,ne,e;
    static int idx;
    static int n, m;
    static boolean[] st;
    static PriorityQueue<int[]> heap = new PriorityQueue<>(new Com());
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        dis = new int[m + 1];
        w = new int[m + 1];
        ne = new int[m + 1];
        st = new boolean[m + 1];
        h = new int[n + 1];
        e = new int[n + 1];
        Arrays.fill(h, -1);
        for(int i = 0; i < m; i++){
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int c = scanner.nextInt();
            add(a,b,c);
        }
        System.out.println(dijkstra());

    }

    private static int dijkstra(){
        Arrays.fill(dis ,1000000000);
        dis[1] = 0;
        heap.add(new int[]{0 ,1});
        while(!heap.isEmpty()){
            int[] t = heap.poll();
            int ver = t[1]; int distance = t[0];
            if(st[ver]) continue;
            st[ver] = true;
            for(int i = h[ver]; i != -1; i = ne[i]){
                int j = e[i];
                if(dis[j] > distance + w[i]){
                    dis[j] = distance + w[i];
                    heap.offer(new int[]{dis[j],j});
                }
            }

        }
        return dis[n] == 1000000000 ? -1 : dis[n];
    }
    private static class Com implements Comparator<int[]>{
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[0] - o2[0];
        }
    }

    private static void add(int a, int b ,int c){
        e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx++;
    }
}
